package ljl.alg.wangzheng_camp.round1.backtrack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 略加思索 直接放弃了
 * */
public class _131_partition {
    
    static class dp {
        boolean[][] dp;
        List<List<String>> res = new ArrayList<>();
        List<String> path = new ArrayList<>();
        public List<List<String>> partition(String s) {
            int n = s.length();
            dp = new boolean[n][n];
    
            for (int i = 0; i < n; i++) {
                Arrays.fill(dp[i], true);
            }
    
            for (int i = n - 1; i >= 0 ; i--) {
                for (int j = i + 1; j < n; j++) {
                    dp[i][j] = s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1];
                }
            }
            dfs(s, 0);
            return res;
        }
        void dfs(String s, int i) {
            if (i == s.length()) {
                res.add(new ArrayList<>(path));
                return;
            }
            for (int j = i; j < s.length(); j++) {
                if (dp[i][j]) {
                    path.add(s.substring(i, j + 1));
                    dfs(s, j + 1);
                    path.remove(path.size() - 1);
                }
            }
        }
    }
    
    /**
     * 和上一个解法一样，就是 dp 数组处理的比较晚
     * */
    static class memorized_backtrack {
        int[][] dp;
        List<List<String>> res = new ArrayList<>();
        List<String> path = new ArrayList<>();
        public List<List<String>> partition(String s) {
            int n = s.length();
            dp = new int[n][n];
            dfs(s, 0);
            return res;
        }
        void dfs(String s, int i) {
            if (i == s.length()) {
                res.add(new ArrayList<>(path));
                return;
            }
            for (int j = i; j < s.length(); j++) {
                if (isPalindrome(s, i, j) == 1) {
                    path.add(s.substring(i, j + 1));
                    dfs(s, j + 1);
                    path.remove(path.size() - 1);
                }
            }
        }
        int isPalindrome(String s, int i, int j) {
            if (dp[i][j] != 0) return dp[i][j];
            if (i >= j) dp[i][j] = 1;
            else if (s.charAt(i) != s.charAt(j)) dp[i][j] = -1;
            else dp[i][j] = isPalindrome(s,i + 1, j - 1);
            return dp[i][j];
        }
    }
    
}
